% introduction
\doclists{} is a new approach in document retrieval, using Generalized \st{s}
\\
Generalized \st{s} are \st{s} that are well suited for dealing with sets of strings, thus for text
corpora, as they possess a number of advantageous properties:

\begin{itemize}
\item Represent large a set of strings in a `compressed' way: Each suffix of a string is only
represented once in the tree.
\item Fast building: New strings can be added in \emph{O(n)} time and space.
\item Fast search: The occurences of a string of length \emph{m} that occurs \emph{n} times in the
text can be retrieved in \emph{O(m + n)} from the tree.
\end{itemize}
Figure \ref{fig:love-tree} shows a suffix tree representing the four sentences `Peter loves Mary',
`John loves Mary', `Mary loves Jane' and `Peter loves Jane'. The special character \emph{\$} is used
to mark the end of a string.
\begin{figure}[h]
\center{\includegraphics[width=.7\textwidth]{pictures/love-tree.png}}
\caption{Example of a suffix tree for 4 sentences}
\end{figure}
\label{fig:love-tree}

For the task of document retrieval, we preferred \st{s} over Suffix \emph{Arrays} as we can use
enriched edges and nodes in it to access information about the stored documents directly via the
tree.

Section \ref{sec:implementation} is giving an overview of our implementation of a \st{} framework in
the JAVA language.
In section \ref{sec:results}, we show results of this framework on a small set of test corpora.
Section \ref{sec:conclusion} concludes this paper and provides a foresight on possible future work.
